Software transactional memory (STM) is a concurrency control mechanism analogous to database transactions for controlling access to shared memory in concurrent computing. A transaction in the context of transactional memory is a piece of code that executes a series of reads and writes to shared memory. STM is used as an alternative to traditional locking mechanisms. Programmers put a declarative annotation (e.g. atomic) around a code block to indicate safety properties they require and the system automatically guarantees that this block executes atomically with respect to other protected code regions. The software transactional memory programming model prevents lock-based priority-inversion and deadlock problems.
While typical STM systems have many advantages, they still require the programmer to be careful in avoiding unintended memory access orderings. For example, the order in which transactions are committed (i.e. commit processing) in a typical STM environment is unconstrained. Transactions race with one another to commit, meaning that whether transaction 1 commits before transaction 2 or after is often a product of the dynamic scheduling of the program (and often by program-specific logic too). Moreover, if two transactions conflict, such as by trying to write to the same piece of memory, then their committing order can be arbitrarily decided based on one of many possible contention management policies. In both of these scenarios, no particular commit order is guaranteed; therefore the burden is on the programmer to make sure that his/her program works correctly with either order. This makes parallel programming very difficult.
One approach to simplifying parallel programming is to automatically parallelize sequential programs, in a manner that guarantees that the semantics of the program are unchanged. In other words, if the sequential program works correctly, so does the parallelized version. Two (separate) variations of this concept to parallelize sequential programs have been termed, respectively, safe futures and speculative loop parallelization. In safe futures, the sequential version of a program might perform “A; B” (that is, do A then do B). The programmer can add an annotation (a “future”) indicating that he or she thinks it might be possible to perform A and B in parallel without changing the program semantics—that A does not read any memory locations that B reads, nor vice-versa. But the system treats this strictly as a “hint” whose validity must be checked. It executes A and B as transactions, and if they conflict, it prevents B from committing if it would be serialized before A. This is an “undesirable” aspect of undetermined commit order referred to above.
Speculative loop parallelization is a similar idea, where the actions performed in the sequential program are the successive iterations of a loop. The programmer (or some static analysis) indicates that it may be advantageous to execute the loop in parallel, and the system runs each iteration of the loop as a parallel transaction, requiring that these transactions commit in the order the iterations would have committed in the original program.